package com.leetcode;

import java.util.ArrayList;

public class PopulateNextRight2 {
	public void connect(TreeLinkNode root) {
		if (root == null) return;
		ArrayList<TreeLinkNode> list = new ArrayList<TreeLinkNode>();
		list.add(root);
		
		while (!list.isEmpty()) {
			ArrayList<TreeLinkNode> swap = new ArrayList<TreeLinkNode>();
			for (int i=0; i<list.size(); i++) {
				TreeLinkNode node = list.get(i);
				if (i < list.size()-1) node.next = list.get(i+1);
				if (node.left!=null) swap.add(node.left);
				if (node.right!=null) swap.add(node.right);
			}
			list = swap;
		}
    }
	
	private class TreeLinkNode {
		TreeLinkNode left;
		TreeLinkNode right;
		TreeLinkNode next;
		int val;
		public TreeLinkNode(int val) {
			this.val = val;
		}
	}
}
